#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

const int MOD = 109;

int main() {
    int n, m;
    cin >> n >> m;

    if (m == 1) {
        cout << n % MOD << endl;
        return 0;
    }

    vector<int> dp(n, 1);  // 初始化第一行，当长度为 1 时，有 n 种方案
    int total = n;  // 总方案数

    for (int len = 2; len <= m; ++len) {
        int new_total = 0;
        for (int cur = 0; cur < n; ++cur) {
            dp[cur] = total - dp[cur];
            dp[cur] = (dp[cur] + MOD) % MOD;  // 防止负数
            new_total = (new_total + dp[cur]) % MOD;
        }
        total = new_total;
    }

    cout << total << endl;
    return 0;
}


//#include <iostream>
//#include <vector>
//#include <cstring>
//using namespace std;
//const int N = 1010;
//bool vis[N][N];
//int n, m;
//int xs, ys, xt, yt;
//int ans = 1e7;
//int disx[4] = { 0,0,1,-1 };
//int disy[4] = { 1,-1,0,0 };
//void dfs(vector<vector<char>>& map, int x, int y, int dis)
//{
//    if (x == (xt - 1) && y == (yt - 1)) {
//        ans = min(ans, dis);
//        return;
//    }
//    vis[x][y] = true;
//    for (int i = 0; i < 4; i++)
//    {
//        int x1 = x + disx[i];
//        int y1 = y + disy[i];
//        if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !vis[x1][y1] && map[x1][y1] != '*') {
//            dfs(map, x1, y1, dis + 1);
//        }
//    }
//    vis[x][y] = false;
//}
//int main() {
//    memset(vis, false, sizeof vis);
//    cin >> n >> m;
//    cin >> xs >> ys >> xt >> yt;
//    vector<vector<char>> map(n + 1, vector<char>(m + 1));
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            cin >> map[i][j];
//        }
//    }
//    dfs(map, xs - 1, ys - 1, 0);
//    if (ans != 1e7) {
//        cout << ans;
//    }
//    else {
//        cout << -1;
//    }
//    return 0;
//}


//#include <iostream>
//#include <vector>
//#include <cstring>
//#include <queue>
//using namespace std;
//const int N = 1010;
//bool vis[N][N];
//int n, m;
//int xs, ys, xt, yt;
//int disx[4] = { 0, 0, 1, -1 };
//int disy[4] = { 1, -1, 0, 0 };
//
//int bfs(vector<vector<char>>& map, int x, int y) {
//    queue<pair<int, int>> q;
//    q.push({ x, y });
//    vis[x][y] = true;
//    int step = 0;
//    while (!q.empty()) {
//        int size = q.size();
//        for (int i = 0; i < size; i++) {
//            //auto [x, y] = q.front();
//            auto tt = q.front();
//            x = tt.first;
//            y = tt.second;
//            q.pop();
//            if (x == xt - 1 && y == yt - 1) {
//                return step;
//            }
//            for (int j = 0; j < 4; j++) {
//                int x1 = x + disx[j];
//                int y1 = y + disy[j];
//                if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !vis[x1][y1] && map[x1][y1] != '*') {
//                    q.push({ x1, y1 });
//                    vis[x1][y1] = true;
//                }
//            }
//        }
//        step++;
//    }
//    return -1; // 如果找不到路径，返回-1
//}
//
//int main() {
//    memset(vis, false, sizeof vis);
//    cin >> n >> m;
//    cin >> xs >> ys >> xt >> yt;
//    vector<vector<char>> map(n, vector<char>(m));
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            cin >> map[i][j];
//        }
//    }
//    int result = bfs(map, xs - 1, ys - 1);
//    cout << result;
//    return 0;
//}


// class Solution {
//   public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 计算成功举办活动需要多少名主持人
//      * @param n int整型 有n个活动
//      * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
//      * @return int整型
//      */
//     int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
//         vector<int> start;
//         vector<int> end;
//         //分别得到活动起始时间
//         for (int i = 0; i < n; i++) {
//             start.push_back(startEnd[i][0]);
//             end.push_back(startEnd[i][1]);
//         }
//         //分别对开始和结束时间排序
//         sort(start.begin(), start.end());
//         sort(end.begin(), end.end());
//         int res = 0;
//         int j = 0;
//         for (int i = 0; i < n; i++) {
//             //新开始的节目大于上一轮结束的时间，主持人不变
//             if (start[i] >= end[j])
//                 j++;
//             else
//                 //主持人增加
//                 res++;
//         }
//         return res;
//     }
// };

//class Solution {
//public:
//    //优先比较开始时间，再比较结束时间
//    static bool comp(vector<int>& a, vector<int>& b) {
//        if (a[0] == b[0])
//            return a[1] < b[1];
//        else
//            return a[0] < b[0];
//    }
//    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
//        sort(startEnd.begin(), startEnd.end(), comp);
//        //小顶堆
//        priority_queue<int, vector<int>, greater<int> > q;
//        //可能有负区间
//        q.push(INT_MIN);
//        for (int i = 0; i < n; i++) {
//            //最近的活动结束时间小于当前活动开始时间
//            if (q.top() <= startEnd[i][0])
//                q.pop();
//            q.push(startEnd[i][1]);
//        }
//        //剩余的活动等于主持人数
//        return q.size();
//    }
//};